perm filename 2[00,BGB]1 blob
sn#041493 filedate 1973-05-16 generic text, type C, neo UTF8
COMMENT ā VALID 00017 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 PAGE 21. FIGURES.
C00004 00003 PAGE 22. THE ALGORITHM: INTRODUCTION.
C00006 00004 PAGE 23. FIGURES.
C00007 00005 PAGE 24. 1. THRESHOLDING.
C00009 00006 PAGE 25. FIGURES. DEKINKING ILLUSTRATED.
C00010 00007 PAGE 26. 2. CONTOURING.
C00015 00008 PAGE 27. FIGURES: NESTING ILLUSTRATED.
C00016 00009 PAGE 28. 3. NESTING.
C00021 00010 PAGE 29. NESTING ILLUSTRATED. CONTINUED.
C00022 00011 PAGE 30. NESTING CONTINUED.
C00023 00012 PAGE 31. FIGURES: RECURSIVE SMOOTHING ILLUSTRATED.
C00024 00013 PAGE 32. 4. SMOOTHING.
C00027 00014 PAGE 33. FIGURES: COMPARING ILLUSTRATED.
C00028 00015 PAGE 34. 5. COMPARING.
C00030 00016 PAGE 35. LAMINA INERTIA TENSOR.
C00031 00017 PAGE 36. PERFORMANCE.
C00032 ENDMK
Cā;
PAGE 21. FIGURES.
PUMP VIDEO
PUMP CONTOURS
PAGE 22. THE ALGORITHM: INTRODUCTION.
CRE consists of five steps: thresholding, contouring,
nesting, smoothing and comparing. The first, second and fourth
steps perform conversions between two different kinds of images;
while the third and the fifth steps compute topological
relationships within a given image representation.
MAJOR OPERATION. OPERAND. RESULT.
1. THRESHOLDING: 6-BIT-IMAGE, 1-BIT-IMAGES.
2. CONTOURING: 1-BIT-IMAGES, VIC-IMAGE.
3. NESTING: VIC-IMAGE, NESTED-VIC-IMAGE.
4. SMOOTHING: VIC-IMAGE, ARC-IMAGE.
5. COMPARING: IMAGE & FILM, FILM.
PAGE 23. FIGURES.
DBA'S TOMBSTONE VIDEO.
DBA'S SMOOTHED CONTOURS.
PAGE 24. 1. THRESHOLDING.
Thresholding, the first and easiest step, consists of two
subroutines, called THRESH and PACXOR. THRESH converts a 6-bit
image into a 1-bit image with respect to a given threshold cut level
between zero for black and sixty three for light. All pixels equal
to or greater than the cut, map into a one; all the pixels less than
the cut, map into zero. The resulting 1-bit image is stored in a bit
array of 216 rows by 288 columns (1728 words) called the PAC
(picture accumulator) which is supposed to remind one of
McCormick's ILLIAC-III. After THRESH, the PAC contains blobs of
bits.
Next, PACXOR copies the PAC into two slightly larger bit
arrays named HSEG and VSEG. Then the PAC is displaced one row or one
column, and is exclusive OR'ed into HSEG and VSEG to compute the
horizontal and vertical border bits of the PAC blobs. Notice, that
this is the very heart of the "edge finder" of CRE. Namely, PACXOR
is the mechanism that converts regions into edges.
PAGE 25. FIGURES. DEKINKING ILLUSTRATED.
PAGE 26. 2. CONTOURING.
Contouring, converts the bit arrays HSEG and VSEG into
vectors and polygons. The contouring itself, is done by a single
subroutine named MKPGON, make polygon. When MKPGON is called, it
looks for the upper most left non-zero bit in the VSEG array. If the
VSEG array is empty, MKPGON returns a NIL. However, when the bit is
found, MKPGON traces and erases the polygonal outline to which that
bit belongs and returns a polygon node with a ring of appropriate
vectors.
To belabor the details (for the sake of later complexities);
the MKGON trace can go in four directions: north and south along
vertical columns of bits in the VSEG array, or east and west along
horizontal rows of the HSEG array. Now the trace starts by heading
south until it hits a "turn"; when heading south MKPGON must check
for first a turn to the east (indicated by a bit in HSEG); next for
no turn (continue south); and last for a turn to the west. When a
turn is encountered MKPGON creates a vector node representing the
run of bits between the previous turn and the present turn. The
trace always ends heading west bound. The outline so traced can be
either the edge of a blob or a hole, the two cases are distinguished
by looking at the VIC-polygon's upper left most pixel in the PAC bit
array.
There are two complexities: contrast
accumulation and dekinking. The contrast of a vector is defined as
(QUOTIENT (DIFFERENCE (Sum of pixel values on one side of the
vector)(Sum of pixel values on the other side ofthe vector)) (length
of the vector in pixels)). Since vectors are always either
horizontal or vertical and are construed as being on the cracks
between pixels; the require summations refer to the obvious pixels
squares on either side of the vector. Notice that this definition of
constrast will always give a positive constrast for vectors of a
blob and negative contrast for the vectors of a hole. More
sophisticated definitions of vector constrast lack this desirable
property.
Finally, dekinking refers to cutting the corners in order to
avoid the jaggies. The jaggies problem involves doing something to a
rectilinear quantized set of segments, to make its linear nature
more evident. The jaggies solution in MKPGON merely involves vernier
positioning the turning locus alittle to the northeast, northwest,
southwest or southeast. The amount of dekinking vernier is greater
for brighter cuts and less for the darker cuts; in order to preserve
the nesting of contours.
PAGE 27. FIGURES: NESTING ILLUSTRATED.
1ST FRAME FLAT NEST.
2ND FRAME GEOMED NEST.
PAGE 28. 3. NESTING.
The nesting problem is to decide whether one contour polygon
is within another. Although easy in the two polygon case; solving
the nesting of many polygons with respect to each other becomes
n-squared expensive in either compute time or in memory space. The
nesting solution in CRE sacrifices memory for speed and requires a
31K array, called the SKY.
CRE's accumulation of a properly nested tree of polygons
depends on the order of threshold cutting going from dark to light.
For each polygon there are two nesting steps: first, the polygon is
placed in the tree of nested polygons by the subroutine INTREE;
second, the polygon is placed in the SKY array by the subroutine
named INSKY.
The SKY array is 216 rows of 288 columns of 18-bit pointers.
The name "SKY" came about because, the array used to represent the
furthest away regions or background, which in the case of a robot
vehicle is the real sky blue. The sky contains vector pointers;
and would be very efficient on on a virtual memory machine
that didn't allocate unused pages of its address space. Whereas
most computers have more memory containers than address space;
computer graphics and vision might be easier to program in a memory
with more address apace than physical space; i.e. an almost empty virtual
memory.
The naive INTREE routine finds the surrounder of a given polygon
by scanning the SKY due east from the upper left most pixel of the
given polygon. The SON of a polygon is always its uppermost left
vector. And next the INSKY routine places pointers to the vectors of
the given polygon in the sky array in the skycells immediately west
or south of each vector.
The sophisticated INTREE routine is complicated by the
proper and efficient handling of multi leveled holes. If the given
polygon, named POLY, has a hole; and if that hole is deeper than the
previous level; then there will be two polygons associated with that
hole, lets call them HOLE1 and HOLE2. Now HOLE2 being of the same
intensity level as Poly and being an ENDO of Poly will has not been
made yet; whereas HOLE1 has been made and placed in Exopoly's
ENDO ring. Thus INTREE must re-scan for the EXO's of all the polygons on
Exopoly's ENDO ring.
On such rescanning there are four cases:
1. No change: the scan returns Exopoly; which is the ENDO's
original EXO.
2. Poly captures Endo; the scan returns Poly indicating
the Endo has been captured by POLY;
3. My brothers fate; the ENDO hits an endo which
is not on the P-list.
4. My fate delayed;
Since deep holes frequently occur in natural images, (even in
images of pears and apples) I was amused to see that not a single deep
hole occurs in the examples in Krakauer's thesis which was about
nested polygon trees of video intensity contours.
PAGE 29. NESTING ILLUSTRATED. CONTINUED.
PAGE 30. NESTING CONTINUED.
PAGE 31. FIGURES: RECURSIVE SMOOTHING ILLUSTRATED.
PAGE 32. 4. SMOOTHING.
In CRE and GEOMED, the term "smoothing" refers more to the
problem of breaking a manifold up into functions, rather than the
problem of fitting functions to measured data.
The smoothing step in CRE, converts the polygons of vertical
and horizontal vectors into polygons of arcs. For the present the
term "arc" means "linear arc" which is a line segment. Fancier arcs:
circular and cubic spline were tried and found expensive to compute
and unwieldly to manipulate; however fancy arcs were doomed by the
fact that after going to all the trouble of implementing and
computing them, there remained the overpowering demand to break them
down again into linear vectors for computing areas, inertia tensors
or mere display buffers.
To start, a ring of two arcs is formed (a bi-gon) with one
arc at the uppermost left and the other at the lowermost right of
the given polygon of vectors. Now the smoothing operation is
recursive; each arc is in one to one correspondece with a list of
vectors; if each point on the list of vectors is close enough to the
approximating arc than MKARC returns the given arc as goo enough;
otherwise MKARC split the arc in two and place a new arc vertex on
the vector vertex tht was furthest away from the original arc.
This manner of smooth collaspes the stair cases of jaggy
quantum edges.
PAGE 33. FIGURES: COMPARING ILLUSTRATED.
1ST Q3
2ND Q4
3RD FUSION Q3 AND Q4
4TH BABY.
PAGE 34. 5. COMPARING.
The compare step of CRE connects the polygons and
arcs of the current image with corresponding polygons and arc
of the previous image. CMPARE solves the problem of correlating
features between two similar images.
CMPARE is composed of four sections:
1. make shape nodes for polygons.
2. compare and connect polygons one to one.
3. compare and connect polygons two to one.
4. compare and connect vertices of two polygons.
first shape nodes for
all the polygons of the current image are computed; second, the
polygons of each level of the current image are compared with
the corresponding level of the previous image for one to one match;
third, the unmated polygons of the current level aree compared with.
PAGE 35. LAMINA INERTIA TENSOR.
PAGE 36. PERFORMANCE.